package 单周赛.september;

import java.util.*;

/**
 *
 */
public class 第362场单周赛 {

    public static void main(String[] args) {

        System.out.println(isReachableAtTime(1, 1, 2, 3, 2));

        第362场单周赛 impl = new 第362场单周赛();

        System.out.println(impl.minimumMoves(new int[][]{
                {2, 0, 2},
                {0, 0, 2},
                {0, 0, 3}
        }));

    }

    /**
     * 哈希表
     */
    public int numberOfPoints(List<List<Integer>> nums) {
        Set<Integer> set = new HashSet<>();

        for (List<Integer> list : nums) {
            for (Integer num = list.get(0); num <= list.get(1); num++) {
                set.add(num);
            }
        }

        return set.size();
    }

    /**
     * 差分数组
     */
    public int numberOfPoints2(List<List<Integer>> nums) {
        int[] diff = new int[102];

        for (List<Integer> list : nums) {
            Integer start = list.get(0), end = list.get(1);
            diff[start]++;
            diff[end + 1]--;
        }
        int ans = 0;
        int curNum = 0;
        for (int di : diff) {
            curNum += di;
            if (curNum > 0) {
                ans++;
            }
        }
        return ans;
    }

    /**
     * 分类讨论
     */
    public static boolean isReachableAtTime(int sx, int sy, int fx, int fy, int t) {
        int minT;
        if (sx == fx && sy == fy) {
            return t != 1;
        } else if (sx == fx) {
            minT = Math.abs(fy - sy);
        } else if (sy == fy) {
            minT = Math.abs(fx - sx);
        } else {
            int a = Math.abs(fy - sy);
            int b = Math.abs(fx - sx) >= a ? Math.abs(fx - sx) - a : Math.abs(fx - sx);
            minT = a + b;

            int c = Math.abs(fx - sx);
            int d = Math.abs(fy - sy) >= c ? Math.abs(fy - sy) - c : Math.abs(fy - sy);
            minT = Math.min(minT, c + d);
        }
        return minT <= t;
    }

    /**
     * 回溯+贪心
     * 将石头移到 0 的位置，如果到 0 的位置有多个，去距离最少
     * 的节点，距离最少的节点可能多个，需要回溯去所有情况的最小
     * 值
     */
    public int minimumMoves(int[][] grid) {
        int ans = Integer.MAX_VALUE;

        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                if (grid[i][j] > 1) {
                    List<int[]> list = getMinDisXy(i, j, grid);
                    for (int[] to : list) {
                        int curDis = Math.abs(to[1] - j) + Math.abs(to[0] - i);
                        grid[i][j]--;
                        grid[to[0]][to[1]]++;

                        ans = Math.min(ans, curDis + minimumMoves(grid));

                        grid[i][j]++;
                        grid[to[0]][to[1]]--;
                    }
                }
            }
        }

        return ans == Integer.MAX_VALUE ? 0 : ans;
    }

    private List<int[]> getMinDisXy(int i, int j, int[][] grid) {
        int minDis = Integer.MAX_VALUE;
        Map<Integer, List<int[]>> map = new HashMap<>();
        for (int x = 0; x < grid.length; x++) {
            for (int y = 0; y < grid.length; y++) {
                if (grid[x][y] == 0) {
                    int curDis = Math.abs(y - j) + Math.abs(x - i);
                    minDis = Math.min(minDis, curDis);
                    List<int[]> list = map.get(curDis);
                    if (list == null) {
                        list = new ArrayList<>();
                        map.put(curDis, list);
                    }
                    list.add(new int[]{x, y});
                }
            }
        }
        return map.get(minDis);
    }

}
